package com.leetcode.two_pointers;

import java.util.List;

/**
 * @author Dennis Li
 * @date 2020/7/18 17:32
 */
public class FindLongestWord_524 {

    public String findLongestWord(String s, List<String> d) {
        // 为空则返回空
        if (s.equals("")) return s;
        // 先对模式串进行排序，长串在前。并且按照字典序升序排序
        d.sort((o1, o2) -> o1.length() != o2.length() ? o2.length() - o1.length() : o1.compareTo(o2));
        for (int k = 0; k < d.size(); k++) {
            // 从第一个串开始匹配，直到匹配到第一个满足条件的
            String temp = d.get(k);
            // 通过双游标对子串进行匹配
            int i = 0, j = 0;
            while (i < s.length() && j < temp.length()) {
                // 当匹配到时，模式串向后一位
                if (s.charAt(i) == temp.charAt(j)) j++;
                i++;
            }
            // 当出现第一个匹配结果，返回
            if (j == temp.length()) return temp;
        }
        return "";
    }

}
